class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}
class QueueNode {
    constructor(pt, dist, prev = null) {
        this.pt = pt;
        this.dist = dist;
        this.prev = prev;
    }
}
function BFS(maze) {
    //init
    const ROW = maze.length;
    const COL = maze[0].length;
    var x0 = maze.findIndex(v => /[<>^v]/.test(v));
    maze = maze.map(v => v.split(''));
    var y0 = maze[x0].findIndex(v => /[<>^v]/.test(v));
    var start_pt = new Point(x0, y0);
    const move = { '>': [0, 1], 'v': [1, 0], '<': [0, -1], '^': [-1, 0], };
    var isValid = (row, col) => (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);
    var isDest = (row, col) => maze[row][col] === ' ' && (row === 0 || row === ROW - 1 || col === 0 || col === COL - 1);
    var visited = Array.from({ length: ROW }, (_, i) => Array.from({ length: COL }, (_, j) => false));
    //bfs
    var q = [];
    var s = new QueueNode(start_pt, 0);
    q.push(s);
    while (q.length) {
        var curr = q.shift();
        for (k of Object.keys(move)) {
            var mov = move[k];
            var row = curr.pt.x + mov[0];
            var col = curr.pt.y + mov[1];
            if (isValid(row, col) && maze[row][col] === ' ' && !visited[row][col]) {
                visited[row][col] = true;
                nxt = new QueueNode(new Point(row, col), curr.dist + 1, curr);
                if (isDest(nxt.pt.x, nxt.pt.y)) return nxt;
                q.push(nxt);
            }
        }
    }
    return [];
}
function escape(maze) {
    var result = BFS(maze);
    if (result.length === 0) return []
    var path = [];
    while (result) {
        path.unshift(result.pt);
        result = result.prev;
    }
    var cur_pt = path.shift();//current position
    var cur_dr = maze[cur_pt.x][cur_pt.y];//current_direction
    const move_dir = { '-1,0': '^', '1,0': 'v', '0,-1': '<', '0,1': '>' }
    const rotate = {
        '>': { 'v': 'R', '^': 'L', '<': 'B' },
        'v': { '^': 'B', '<': 'R', '>': 'L' },
        '<': { '>': 'B', '^': 'R', 'v': 'L' },
        '^': { 'v': 'B', '<': 'L', '>': 'R' }
    }
    var out = []
    for (p of path) {
        var diff = (p.x - cur_pt.x) + ',' + (p.y - cur_pt.y);
        var forward = move_dir[diff];
        if (forward != cur_dr) {
            console.log(rotate[cur_dr][forward])
            out.push(rotate[cur_dr][forward])
        }
        out.push('F')
        cur_dr = forward;
        cur_pt = p;
    }
    return out;
}
